import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-06
 * Time: 8:54
 */

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}


public class Solution {
    public Node dfs(Node head){
        Node prev = null;
        Node cur = head;
        Node next = null;
        while (cur != null){
            // 有子节点
            if (cur.child != null){
                // 先与后面的节点断开连接
                next = cur.next;
                if (next != null){
                    next.prev = null;
                }
                // 与下一级链表进行连接
                cur.next = cur.child;
                cur.child.prev = cur;
                // 不要忘了将 child 置空
                cur.child = null;
                // 得到下一级链表的尾部
                Node tail = dfs(cur.next);
                // 下一级链表与本级链表进行连接
                tail.next = next;
                // 如果上级的 next 为空, 那么要返回的就是下一级的尾指针
                if (next == null){
                    return tail;
                }
                next.prev = tail;
                prev = cur;
                cur = next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        // 返回的是本级链表的结尾
        return prev;
    }

    public Node flatten(Node head) {
        dfs(head);
        return head;
    }
}
